package com.singzi.algorithm;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TopSort {
    public static void main(String[] args) {
        int numCourses = 3;
        int[][] prerequisites = {{1,0}};
        SolutionTopSort solutionTopSort = new SolutionTopSort();
        solutionTopSort.canFinish(3, prerequisites);
    }
}
class SolutionTopSort {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        Stack<Integer> stack = new Stack<>();
        List<List<Integer>> coursesList = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            coursesList.add(new ArrayList<Integer>());
        }

        int []courses = new int[numCourses];
        int n = 0;
        for(int[] nums:prerequisites){
            courses[nums[1]]++;
            coursesList.get(nums[0]).add(nums[1]);
        }
        for (int i = 0; i < numCourses; i++) {
            if(courses[i] == 0) stack.push(i);
        }
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            n++;
            for(Integer in:coursesList.get(pop)){
                courses[in]--;
                if(courses[in] == 0){
                    stack.push(in);
                }
            }
        }
//        System.out.println(n);
        return n == numCourses;
    }
}